#ifndef _OCTREE_H_INCLUDED_
#define _OCTREE_H_INCLUDED_

#include "boundingbox.h"
#include "boundingsphere.h"
#include "frustumcullingtype.h"

#include <vector>

template<typename T>
class Octree {
public:
    Octree(BoundingBox* boundingBox, float treshold, const Octree<T>* parent);
    virtual ~Octree(void);
    BoundingBox* GetBoundingBox() const;
    BoundingSphere* GetBoundingSphere() const;
    vector<Octree<T>*>* GetChildren() const;
    T GetItem() const;
    void SetItem(T val);
    const Octree<T>* FindChild(Vector4 position) const;
    vector<Octree<T>*>* FindVisible();
protected:
    BoundingBox* boundingBox;
    BoundingSphere* boundingSphere;
    vector<Octree<T>*>* children;
    T item;
    const Octree<T>* parent;
    float treshold;
    Octree<T>* Create(float minX, float minY, float minZ, float maxX, float maxY, float maxZ) const;
    void FindVisible(Octree<T>* root, vector<Octree<T>*>** visible);
};

template<typename T>
Octree<T>::Octree(BoundingBox* boundingBox, float treshold, const Octree<T>* parent) :
        boundingBox(boundingBox), treshold(treshold), parent(parent) {
    this->children = (vector<Octree*>*)new vector<Octree*>();

    Octree<T>* octree = NULL;
    this->item = NULL;
    float minX = this->boundingBox->min.x;
    float minY = this->boundingBox->min.y;
    float minZ = this->boundingBox->min.z;
    float maxX = this->boundingBox->max.x;
    float maxY = this->boundingBox->max.y;
    float maxZ = this->boundingBox->max.z;
    float halfX = minX + (maxX - minX) / 2;
    float halfY = minY + (maxY - minY) / 2;
    float halfZ = minZ + (maxZ - minZ) / 2;

    this->boundingSphere = new BoundingSphere();
    this->boundingSphere->center.x = halfX;
    this->boundingSphere->center.y = halfY;
    this->boundingSphere->center.z = halfZ;
    this->boundingSphere->center.w = 1;
    this->boundingSphere->radius = (this->boundingBox->max - this->boundingBox->min).Length();

    if (maxX - minX <= treshold || maxY - minY <= treshold || maxZ - minZ <= treshold) {
        return;
    }

    octree = this->Create(minX, minY, minZ, halfX, halfY, halfZ);
    this->children->push_back(octree);
    octree = this->Create(halfX, minY, minZ, maxX, halfY, halfZ);
    this->children->push_back(octree);
    octree = this->Create(minX, halfY, minZ, halfX, maxY, halfZ);
    this->children->push_back(octree);
    octree = this->Create(halfX, halfY, minZ, maxX, maxY, halfZ);
    this->children->push_back(octree);
    octree = this->Create(minX, minY, halfZ, halfX, halfY, maxZ);
    this->children->push_back(octree);
    octree = this->Create(halfX, minY, halfZ, maxX, halfY, maxZ);
    this->children->push_back(octree);
    octree = this->Create(minX, halfY, halfZ, halfX, maxY, maxZ);
    this->children->push_back(octree);
    octree = this->Create(halfX, halfY, halfZ, maxX, maxY, maxZ);
    this->children->push_back(octree);
}

template<typename T>
Octree<T>::~Octree(void) {
}

template<typename T>
BoundingBox* Octree<T>::GetBoundingBox() const {
    return this->boundingBox;
}

template<typename T>
BoundingSphere* Octree<T>::GetBoundingSphere() const {
    return this->boundingSphere;
}

template<typename T>
vector<Octree<T>*>* Octree<T>::GetChildren() const {
    return this->children;
}

template<typename T>
T Octree<T>::GetItem() const {
    return this->item;
}

template<typename T>
void Octree<T>::SetItem(T val) {
    this->item = val;
}

template<typename T>
Octree<T>* Octree<T>::Create(float minX, float minY, float minZ, float maxX, float maxY, float maxZ) const {
    BoundingBox* boundingBox = new BoundingBox();
    boundingBox->min.x = minX;
    boundingBox->min.y = minY;
    boundingBox->min.z = minZ;
    boundingBox->max.x = maxX;
    boundingBox->max.y = maxY;
    boundingBox->max.z = maxZ;

    return new Octree<T>(boundingBox, this->treshold, this);
}

template<typename T>
const Octree<T>* Octree<T>::FindChild(Vector4 position) const {
    if (!this->boundingBox->isPointInside(position)) {
        return NULL;
    }

    for (vector<Octree*>::iterator it = this->children->begin(); it != this->children->end(); ++it) {
        const Octree<T>* child = (*it)->FindChild(position);
        if (child != NULL) {
            return child->FindChild(position);
        }
    }

    return this;
}

template<typename T>
vector<Octree<T>*>* Octree<T>::FindVisible() {
    vector<Octree*>* visible = new vector<Octree*>();
    this->FindVisible(this, &visible);
    return visible;
}

template<typename T>
void Octree<T>::FindVisible(Octree<T>* root, vector<Octree<T>*>** visible) {
    FrustumCullingType sphereCulling = Pipeline.SphereInFrustum(root->GetBoundingSphere());
    if (sphereCulling == FRUSTUMCULLINGTYPE_NONE) {
        return;
    } else if (sphereCulling == FRUSTUMCULLINGTYPE_FULL) {
        (*visible)->push_back(root);
    } else {
        FrustumCullingType culling = Pipeline.BoxInFrustum(root->GetBoundingBox());
        if (culling == FRUSTUMCULLINGTYPE_FULL || (culling == FRUSTUMCULLINGTYPE_PARTIAL && root->GetChildren()->size() == 0)) {
            (*visible)->push_back(root);
        } else if (culling == FRUSTUMCULLINGTYPE_PARTIAL) {
            for (vector<Octree<T>*>::iterator it = root->GetChildren()->begin(); it != root->GetChildren()->end(); ++it) {
                this->FindVisible(*it, visible);
            }
        } else {
        }
    }
}

#endif
